#ifndef GRAPH_H
#define GRAPH_H

#include <stdio.h>
#include <vector>
#include <list>

#define INF 0x7fffffff

struct Edge {
  Edge(int v, int dist) : v(v), dist(dist) { }
  Edge() : v(-1), dist(INF) { }

  int v;
  int dist;
};

typedef std::list<Edge> EdgeList;

class Graph {
public:
  Graph(int n_vertices) : edgelists_(n_vertices) { }

  void AddEdge(int i, int j, int dist) {
    edgelists_[i].push_back(Edge(j, dist));
    edgelists_[j].push_back(Edge(i, dist));
  }

  void AddDirectedEdge(int i, int j, int dist) {
    edgelists_[i].push_back(Edge(j, dist));
  }

  size_t n_vertices() const { return edgelists_.size(); }
  const EdgeList &neighbors(int i) const { return edgelists_[i]; }
private:
  std::vector<EdgeList> edgelists_;
};

#endif // GRAPH_H

